import collections


class Solution(object):
    def pathSum(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        max_depth = nums[-1] // 100
        last_d = collections.defaultdict(int)
        now_depth = nums[-1] // 100
        index = n - 1
        total = 0
        while index >= 0:
            if nums[index] // 100 == now_depth:
                if now_depth == max_depth:
                    total += nums[index] % 10
                    node_id = (nums[index] - now_depth * 100) // 10
                    last_d[(node_id + 1) // 2] += 1
                else:
                    node_id = (nums[index] - now_depth * 100) // 10
                    if node_id not in now_d:
                        now_d[node_id] += 1
                        total += (nums[index] % 10) * now_d[node_id]
                    else:
                        total += (nums[index] % 10) * now_d[node_id]
                    last_d[(node_id + 1) // 2] += now_d[node_id]
                index -= 1
            else:
                now_depth = nums[index] // 100
                now_d = last_d
                last_d = collections.defaultdict(int)
        return total


data = Solution()
nums = [111, 217, 221, 315, 415]
print(data.pathSum(nums))
